| 科目名 |
□データ構造とアルゴリズムⅢ
|
| 担当教員 |
古井 陽之助
|
| 対象学年 |
3年
|
クラス |
[256]
|
| 講義室 |
１２１０８教室
|
開講学期 |
前期
|
| 曜日・時限 |
金３
|
単位区分 |
選択
|
| 授業形態 |
|
単位数 |
2
|
| 準備事項 |
|
| 備考 |
|
|
講義概要/Class Outline
|
コンピュータを用いると、大量のデータを効率よく処理できるのみならず、精度の高い数値計算や、複雑な構造を持つデータの処理が可能になる。「データ構造とアルゴリズムI」「同II」までは大量のデータを効率よく処理するためのデータ構造やアルゴリズムを扱った。本講義ではこれらの講義に続き、誤差を考慮した数値計算のアルゴリズム、ハッシュ表、ヒープ、ヒープソート、グラフの表現と応用を取り上げる。
|
|
講義計画 /Class Structure
|
| 回 |
内容
|
|
1
|
数値計算と誤差(1) 計算機内部の数値表現
|
|
2
|
数値計算と誤差(2) 計算機を用いた数値計算での様々な誤差
|
|
3
|
数値計算と誤差(3) 誤差を考慮した数値計算
|
|
4
|
応用データ構造(1) 集合の表現と操作
|
|
5
|
応用データ構造(2) ハッシュ関数
|
|
6
|
応用データ構造(3) ハッシュ表
|
|
7
|
応用データ構造(4) ヒープ
|
|
8
|
応用アルゴリズム ヒープソート
|
|
9
|
グラフの表現 隣接行列と隣接リスト
|
|
10
|
グラフの応用(1) 深さ優先探索と幅優先探索
|
|
11
|
グラフの応用(2) 最短路アルゴリズム
|
|
12
|
グラフの応用(3) 最小スパニング木
|
|
13
|
まとめ(1)
|
|
14
|
まとめ(2)
|
|
| 学習・教育目標/Class Target |
1. 数値計算と誤差の基礎的な事項について理解し、誤差を考慮した数値計算のプログラムを作成できる。
2. ハッシュの基本概念とハッシュ表の操作を理解し、ハッシュ表の応用ができる。
3. ヒープとヒープソート、グラフの表現を理解し、グラフの応用ができる。
|
| 評価基準/GradingCriteria |
秀：評価方法の総点が満点の9割以上
優：評価方法の総点が満点の8割以上
良：評価方法の総点が満点の7割以上
可：評価方法の総点が満点の6割以上
|
| 評価方法/GradingMethod |
定期試験、小テスト、演習の合計点（比率は3:1:1）を総点とする。
|
| 受講上の注意/Class Rules |
関連科目を復習しておくこと。貸与ノートパソコンを忘れずに持ってくること。
|
| 受講制限/Prerequisit |
|
| 関連する科目/Related Class |
プログラミング基礎、データ構造とアルゴリズムI、データ構造とアルゴリズムII、離散数学III-A、離散数学III-B
|
| 教科書/Text |
| 著者名
|
権藤 克彦
|
| 著書名
|
Javaによるプログラミング入門（1年次に購入済みの教科書を使用）
|
| 出版社名
|
サイエンス社
|
| ISBNコード |
978-4-7819-0942-4
|
|
| 指定図書/Assigned Books |
| 著者名
|
五十嵐 健夫
|
| 著書名
|
データ構造とアルゴリズム
|
| 出版社名
|
数理工学社
|
| ISBNコード |
978-4-9016-8349-4
|
| 著者名
|
近藤 嘉雪
|
| 著書名
|
Javaプログラマのためのアルゴリズムとデータ構造
|
| 出版社名
|
ソフトバンク
|
| ISBNコード |
978-4-7973-2660-4
|
| 著者名
|
Robert Lafore， 岩谷 宏(翻訳)
|
| 著書名
|
Javaで学ぶアルゴリズムとデータ構造
|
| 出版社名
|
ソフトバンク
|
| ISBNコード |
978-4-7973-0694-1
|
|
| 参考文献/Bibliography |
| 著者名
|
伊藤 正夫， 藤野 和建
|
| 著書名
|
数値計算の常識
|
| >出版社名
|
共立出版
|
| ISBNコード |
978-4-3200-1343-8
|
| 著者名
|
奥村 晴彦， 杉浦 方紀， 津留 和生， 首藤 一幸， 土村 展之
|
| 著書名
|
Javaによるアルゴリズム事典
|
| >出版社名
|
技術評論社
|
| ISBNコード |
978-4-7741-1729-4
|
| 著者名
|
T. H. Cormen， C. Stein， R. L. Rivest， C. E. Leiserson， 浅野 哲夫(翻訳)， 岩野 和生 (翻訳)ほか
|
| 著書名
|
アルゴリズムイントロダクション改訂2版 第1巻 数学的基礎とデータ構造
|
| >出版社名
|
近代科学社
|
| ISBNコード |
978-4-7649-0334-0
|
| 著者名
|
T. H. Cormen， C. Stein， R. L. Rivest， C. E. Leiserson， 浅野 哲夫(翻訳)， 岩野 和生 (翻訳)ほか
|
| 著書名
|
アルゴリズムイントロダクション改訂2版 第2巻 アルゴリズムの設計と解析手法
|
| >出版社名
|
近代科学社
|
| ISBNコード |
978-4-7649-0335-7
|
|
